package algorithms.leaning.class11;

import common.bean.TreeNode;
import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 使用层序遍历对二叉树进行序列化和反序列化
 *
 * @author guichang
 * @date 2021/6/9
 */

@SuppressWarnings("all")
public class Code3_二叉树_序列化_层序遍历 {
    public static void main(String[] args) {
        TreeNode oNode = MyUtil.createTreeNode(1, null, 2, 3);
        LinkedList<Integer> list = encode(oNode);
        MyUtil.print("序列化后：");
        MyUtil.print(list);
        TreeNode nNode = decode(list);
        MyUtil.print("反序列化后：");
        MyUtil.printTreeNode(nNode);
    }

    /**
     * 序列化
     */
    public static LinkedList<Integer> encode(TreeNode node) {
        LinkedList<Integer> list = new LinkedList<>();
        // 层序遍历用
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(node);
        list.offer(node.val); // 提前加入
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            // 仅加入左右节点
            if (cur.left != null) {
                queue.offer(cur.left);
                list.offer(cur.left.val);
            } else {
                list.offer(null);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                list.offer(cur.right.val);
            } else {
                list.offer(null);
            }
        }
        return list;
    }

    /**
     * 反序列化
     */
    public static TreeNode decode(LinkedList<Integer> list) {
        // 头节点
        TreeNode head = createSingleTreeNode(list.poll());
        // 建TreeNode用
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(head);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            // 左节点
            cur.left = createSingleTreeNode(list.poll());
            if (cur.left != null) {
                // 不为空则放入队列中继续建树
                queue.offer(cur.left);
            }
            // 右节点
            cur.right = createSingleTreeNode(list.poll());
            if (cur.right != null) {
                // 不为空则放入队列中继续建树
                queue.offer(cur.right);
            }
        }
        return head;
    }

    private static TreeNode createSingleTreeNode(Integer value) {
        return value == null ? null : new TreeNode(value);
    }
}